#include "graph.h"
#include "func_generales.h"
#include <limits.h>

using namespace std;

#define MAX_ATTEMPT 50

int FindV(int ** d, int l, list<int> * R, int & v, int & i) {
    v = -1;
    i = l - 1; // mayor diametro
    int d_i_v = INT_MAX;

    for (int j = 0; j < l; j++) {
        for (list<int>::iterator it = R->begin(); it != R->end(); ++it) {
            if (d[j][*it] <= d_i_v && (d_i_v != d[j][*it] || j <= i)) {
                v = *it;
                i = j;
                d_i_v = d[j][*it];
            }
        }
    }

    //cout << "v, i: " << v+1 << " " << i << endl;

    if (v == -1) return -1; // nunca deberia llegar aca
    return 0;
}

int FindI(int ** d, int l, int dst) {
    int i = -1;
    int d_i_dst = INT_MAX;
    for (int j = 0; j < l; j++) {
        if (d[j][dst] < d_i_dst && (d[j][dst] != d_i_dst || j <= i)) {
            d_i_dst = d[j][dst];
            i = j;
        }
    }

    return i;
}

Path * RestrictedShortestPath(Graph * Gp, int src, int dst, int l) {
    list<int> * U = new list<int>();
    list<int> * R = new list<int>();
    int ** d = new int*[l];
    int ** ant = new int*[l];
    int v;
    int di;

    for (int i = 0; i < l; i++) {
        ant[i] = new int[Gp->sizeG];
        d[i] = new int[Gp->sizeG];

        for (int j = 0; j < Gp->sizeG; j++) {

            if (i == 0 && Gp->actived_node[j] && j != src)
                U->push_front(j);

            if (i == 0 && Gp->actived_node[j] && GetMatrix(Gp->E, src, j))
                R->push_front(j);

            if (Gp->actived_node[j]) {
                if (j == src) {
                    d[i][j] = 0;
                    ant[i][j] = -1;
                } else if (GetMatrix(Gp->E, src, j)) {
                    d[i][j] = GetMatrix(Gp->C, src, j) + Gp->W[src] + Gp->W[j];
                    ant[i][j] = src;
                } else {
                    d[i][j] = INT_MAX;
                    ant[i][j] = -1;
                }
            }
        }
    }

    while (!R->empty() && 1 < l) {

        if (FindV(d, l, R, v, di)) {
            return new Path();
        }

        U->remove(v);
        R->remove(v);
        list<int> * neighbors = Gp->GetNeighbors(v, U);

        for (list<int>::iterator itw = neighbors->begin(); itw != neighbors->end(); ++itw) {
            for (int j = di + 1; j < l; j++) {
                if ((d[j - 1][v] < INT_MAX) && ((d[j - 1][v] + GetMatrix(Gp->C, v, *itw) + Gp->W[*itw]) <= d[j][*itw])) {
                    d[j][*itw] = d[j - 1][v] + GetMatrix(Gp->C, v, *itw) + Gp->W[*itw];
                    ant[j][*itw] = v;
                }
            }

            if (d[l - 1][*itw] < INT_MAX) {
                if (R->end() == find(R->begin(), R->end(), *itw)) R->push_back(*itw);
            }
        }

        DeleteListInt(neighbors);

    }

    Path * path = new Path();

    int aux_i = FindI(d, l, dst);
    if (aux_i > -1) {
        int j = dst;
        while (ant[aux_i][j] >= 0) {
            path->path->push_front(j);
            j = ant[aux_i][j];
        }
        path->path->push_front(src);
    }


    DeleteMatrix(ant, l);
    DeleteMatrix(d, l);
    U->clear();
    R->clear();
    delete U;
    delete R;

    return path;
}

list<Path*> * Graph::GetKPathsBetween(int src, int dst, int k, int l) {

    list<Path*> * paths = new list<Path*>();
    Path * path;
    int attemp = 0;
    list<pair<int, int>* > * edges = new list<pair<int, int>* >();
    pair<int, int>* edge;


    while (paths->size() < (unsigned int) k && attemp < MAX_ATTEMPT) {
        path = RestrictedShortestPath(this, src, dst, l);

        if (path->IsEmpty()) {
            delete path;
            attemp++;

            for (list<pair<int, int>*>::iterator it = edges->begin(); it != edges->end(); ++it) { // habilito las aristas de nuevo
                SetMatrix(E, (*it)->first, (*it)->second, 1);
            }

            CleanListPairInt(edges);

            for (list<Path *>::iterator it = paths->begin(); it != paths->end(); ++it) { // deshabilito nuevas aristas para volver a intentar
                edge = RandomEdge(*it);
                edges->push_front(edge);
                SetMatrix(E, edge->first, edge->second, 0);
            }
        } else {
            paths->push_front(path);
            edge = RandomEdge(path);
            edges->push_front(edge);
            //// cout << "Edge " << "(" << edge->first << ", " << edge->second << ")"<<endl;
            SetMatrix(E, edge->first, edge->second, 0); // inablito la arista, para que el RSP no encuntre el mismo camino
        }
    }

    for (list<pair<int, int>*>::iterator it = edges->begin(); it != edges->end(); ++it) { // habilito las aristas de nuevo
        SetMatrix(E, (*it)->first, (*it)->second, 1);
    }

    DeleteListPairInt(edges);

    return paths;
}

list<list<int>*>* Graph::caminoNodoDisjuntos(int source, int dest) {
    Graph* copia = new Graph(this);
    list<list<int>*>* listaCaminosNodoDisjuntos = new list<list<int>*>;
    Path* p;
    //    cout << "Source: " << source << endl;
    //    cout << "Destino: " << dest << endl;
    //    cout << "LargoGrafo: " << this->sizeG << endl;
    p = RestrictedShortestPath(copia, source, dest, this->sizeG);
    while (!p->IsEmpty()) {
        listaCaminosNodoDisjuntos->push_back(p->path);
        copia->SubstractWithoutExtremes(p);
        p = RestrictedShortestPath(copia, source, dest, this->sizeG);
    }
    delete copia;
    return listaCaminosNodoDisjuntos;
}